A conventional network switching appliance receives packets of a flow onto one of several input ports. For each packet, the switching appliance examines parts of the headers of the packet, and from these headers determines the flow to which the packet belongs. For each such flow, the switching appliance has been preconfigured so that it will output packets of that flow onto the predetermined one of the output ports. Once the flow of a packet has been identified, the switching appliance outputs the packet onto the appropriate output port in accordance with how the switching appliance has been preconfigured.
One type of conventional network switching appliance may operate to switch several millions of flows. The switching appliance may receive packets at a 10 Gbps rate or more on each of several input ports, and may output the packets onto several output ports at a 10 Gbps rate or more onto each of one or more output ports. In such a switching appliance, the flow of a packet is determined by a flow key, where the flow key is a concatenation or a combination of the IP source address of the packet, the IP destination address of the packet, the TCP source port of the packet, the TCP destination port of the packet, and other parameters. These identifying values are extracted from the headers of an incoming packet and are concatenated or otherwise combined to form the flow key. A hash algorithm is then used to convert the flow key into a shorter hash value. The hash value is then used as an index into a hash table of hash entries. The hash algorithm may convert multiple different flow keys into the same hash value, so the hash table will be indexed the same way to point to the same hash entry despite the packets being of these different flows. The hash entry stores the full flow key, and also stores or points to or is otherwise associated with certain associated lookup information. The lookup information may, for example, indicate an output port of the switching appliance from which packets of the flow are to be output.
Once the hash value has been determined from the incoming packet, and once the hash value has been used to identify a hash entry in the hash table, then the flow key stored in the identified hash entry is extracted and is compared with the original flow key generated from the packet in order to determine whether the hash entry is the correct entry for the packet. If the hash entry is the correct hash entry for the packet, then the flow key stored in the hash entry will match the flow key from which the hash value was computed. If a second flow key results in a hash value that points to the same hash entry of the flow table, then the hash entry of the table points to a second hash entry for this second flow key. The second hash entry is not in the table per se, but rather is linked to the hash entry of the table to form a linked list of hash entries. If the flow key of the hash entry of the hash table has been checked and determined not to match the original flow key of the packet, then the second hash entry of the linked list is consulted. The flow key of this second hash entry is compared with the original flow key to determine if it matches. Depending on the particular flow keys of the particular flows, and depending on the hash table size and the hash algorithm used, some hash table entries may be empty, whereas others may be populated and may be the beginning of linked lists of hash entries.
Processing continues in this way checking the flow keys stored in the hash entries of the linked list until the flow key of a hash table entry is found to match the original flow key of the packet. When the match is found, the associated lookup information is extracted and is used to determine how to forward the packet. Ways are sought of improving this flow key to lookup information lookup operation in a switching appliance.